Field of the Invention
This invention relates to the field of data processing. More particularly, this invention relates to data processing systems incorporating a cache memory. Cache memories incorporating content addressable memories (CAMs) and associated RAM memories are known within data processing systems. A CAM may be used to provide storage for a TAG within a cache memory system. A CAM allows an input value to be compared in parallel with a plurality of values stored in respective content addressable storage rows within the CAM. If a content addressable storage row is storing a content addressable data word matching the input data value, then a hit signal is generated for that row signalling a match. The hit signal is then used to select a corresponding cache row within the RAM of the cache memory that is storing data values having memory addresses indicated by the TAG value.
Another part of a cache memory is the victim select circuitry that controls which cache data is to be removed from the cache memory when new cache data needs to be stored into the cache memory and the cache memory is already full. Various victim selection strategies are known, such as random, least recently used and round-robin.
A constant aim within data processing systems is to reduce the size of the circuits. This increases speed, reduces cost and reduces power consumption as well as providing other advantages.
Viewed from one aspect the present invention provides apparatus for processing data having a cache memory, said cache memory comprising:
(i) a plurality of content addressable storage rows, each content addressable storage row containing a plurality of content addressable bit storage cells and serving to store a content addressable data word;
(ii) a plurality of bit lines connecting corresponding content addressable bit storage cells in different content addressable storage rows such that an input data word on said plurality of bit lines is compared in parallel with the contents of each connected content addressable storage row;
(iii) a plurality of hit lines, each content addressable storage row having an associated hit line upon which a hit signal is asserted if said input data word matches a content addressable data word stored within said content addressable storage row;
(iv) a plurality of cache data rows each storing a row of cache data, said content addressable memory serving to store address data to identify memory addresses for corresponding rows of cache data such that a hit signal generated on a hit line in said content addressable memory enables access to a corresponding cache data row within said cache memory; and
(v) an index decoder for decoding an index value to generate a select signal for selecting a content addressable storage row and a cache data row for replacement within said cache memory; wherein
(vi) said select signal is passed to said cache data row via a corresponding one of said hit lines.
It is known within cache memory systems to provide signal lines running across each content addressable storage row. These may be a hit line for indicating a match with a TAG value, a write enable for enabling writing to a content addressable storage row and a corresponding cache data row, and a read enable to enable reading from a content addressable storage row. Either the hit signal or the read enable signal needs to be passed to a cache data row and so a multiplexer is typically provided between the CAM and the cache RAM to select one of these signals to be passed to the RAM. Such a multiplexer may be on the critical path limiting the maximum speed of operation of the cache memory and accordingly its presence is disadvantageous. A further disadvantage of this known arrangement is that the three separate signal lines passing across the content addressable storage row limit the minimum size that can be achieved for the content addressable storage row.
The present invention recognises both of the above problems and realises that they may be overcome by using the hit line traversing the content addressable storage row to also pass a victim select signal to a victim cache data row. This can reduce the number of signal lines passing across each content addressable storage row from three to two and remove a multiplexer from the critical path.
In preferred embodiments of the invention access enable lines are also provided across each content addressable storage row to provide access to the contents of the content addressable memory when it is desired that this should be independent of any signal upon the hit line.
The content addressable memory may also have valid and dirty bits associated with each row and in this circumstance it is desirable that a selectable connection is provided for coupling a hit signal to enable access to any relevant valid and dirty bit in a matching row.
Viewed from another aspect the present invention provides a method of processing data using a cache memory, said comprising method comprising the steps of:
(i) storing content addressable data words within a plurality of content addressable storage rows, each content addressable storage row containing a plurality of content addressable bit storage cells;
(ii) connecting corresponding content addressable bit storage cells in different content addressable storage rows with a plurality of bit lines such that an input data word on said plurality of bit lines is compared in parallel with the contents of each connected content addressable storage row;
(iii) providing a plurality of hit lines, each content addressable storage row having an associated hit line upon which a hit signal is asserted if said input data word matches a content addressable data word stored within said content addressable storage row;
(iv) providing a plurality of cache data rows each storing a row of cache data, said content addressable memory serving to store address data to identify memory addresses for corresponding rows of cache data such that a hit signal generated on a hit line in said content addressable memory enables access to a corresponding cache data row within said cache memory; and
(v) providing an index decoder for decoding an index value to generate a select signal for selecting a content addressable storage row and a cache data row for replacement within said cache memory; wherein
(vi) said select signal is passed to said cache data row via a corresponding one of said hit lines.
The present invention may also be used to address the problem of increasing processing speed when a block transfer of data from one memory location to another memory location is required with that data then being used from the new location. Known systems have required the data to be read from the main memory to the processor, written back from the processor to the new address within the main memory and finally read from the main memory or processor back to the cache memory with the associated TAG for the new memory location ready for further use. This is a relatively slow process.
Viewed from another aspect the present invention provides apparatus for processing data having a cache memory, said cache memory comprising:
(i) a plurality of content addressable storage rows, each content addressable storage row containing a plurality of content addressable bit storage cells and serving to store a content addressable data word;
(ii) a plurality of bit lines connecting corresponding content addressable bit storage cells in different content addressable storage rows such that an input data word on said plurality of bit lines is compared in parallel with the contents of each connected content addressable storage row;
(iii) a plurality of hit lines, each content addressable storage row having an associated hit line upon which a hit signal is asserted if said input data word matches a content addressable data word stored within said content addressable storage row;
(iv) a plurality of access enable lines, each content addressable storage row having an associated access enable line upon which an access signal may be asserted to allow a content addressable data word stored within said content addressable storage row to be accessed;
(v) a plurality of cache data rows each storing a row of cache data, said content addressable memory serving to store address data to identify memory addresses for corresponding rows of cache data such that a hit signal generated on a hit line in said content addressable memory enables access to a corresponding cache data row within said cache memory;
(vi) wherein, in an access mode, a connection is provided between a hit line for a content addressable storage row and an access enable line for that content addressable storage row such that an input data word on said bit lines can be compared with said content addressable data words within said plurality content addressable storage rows and if a match occurs for a content addressable storage row generating a hit signal to enable access to that row by passing said hit signal to serve as an access enable signal upon an access enable line.
Providing a connection between the hit signal line and the access enable signal line allows the data stored within the content addressable memory to be manipulated even when its location within the content addressable memory is not known, i.e. the content addressable memory can first be searched to find the data item in question to generate a hit signal and then this hit signal be redirected to provide access for manipulation to the relevant row within the content addressable memory. This feature allows the data stored within a content addressable memory to be manipulated in situ in a manner not previously possible. One example of such a manipulation is to modify the TAG value associated with a row of cache data while the cache data is still stored within the cache memory RAM. More specifically, words from a first memory location can be read to the cache memory, the TAG value stored within the content addressable memory found and modified to point to a second memory location and the cache words directly from the cache memory using their associated second memory address without having to first be written back to the main memory. The dirty bit associated with a cache memory row that is so modified can be set to ensure that when the cache data is removed from the cache memory it is written back to the main memory such that the integrity of the system is maintained.
Viewed from a further aspect the invention provides a method of processing data using a content addressable memory, said method comprising the steps of:
(i) storing content addressable data words within a plurality of content addressable storage rows, each content addressable storage row containing a plurality of content addressable bit storage cells;
(ii) connecting corresponding content addressable bit storage cells in different content addressable storage rows with a plurality of bit lines such that an input data word on said plurality of bit lines is compared in parallel with the contents of each connected content addressable storage row;
(iii) providing a plurality of hit lines, each content addressable storage row having an associated hit line upon which a hit signal is asserted if said input data word matches a content addressable data word stored within said content addressable storage row;
(iv) providing a plurality of access enable lines, each content addressable storage row having an associated access enable line upon which an access signal may be asserted to allow a content addressable data word stored within said content addressable storage row to be accessed;
(v) wherein, in an access mode, a connection is provided between a hit line for a content addressable storage row and an access enable line for that content addressable storage row such that an input data word on said bit lines can be compared with said content addressable data words within said plurality content addressable storage rows and if a match occurs for a content addressable storage row generating a hit signal to enable access to that row by passing said hit signal to serve as an access enable signal upon an access enable line.
The above, and other objects, features and advantages of this invention will be apparent from the following detailed description of illustrative embodiments which is to be read in connection with the accompanying drawings.